package leetcode.editor.cn;

import java.util.Arrays;

public class _34_FindFirstAndLastPositionOfElementInSortedArray {
    public static void main(String[] args) {
        Solution solution = new _34_FindFirstAndLastPositionOfElementInSortedArray().new Solution();
        int[] nums = {1};
        int[] ints = solution.searchRange(nums, 0);
        System.out.println(Arrays.toString(ints));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        private int findLeft(int[] nums, int target) {
            int l = 0, r = nums.length - 1;
            while (l <= r) {
                int mid = l + (r - l) / 2;
                if (target <= nums[mid]) {
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            }
            // target 太大 || 不存在
            if (l == nums.length || nums[l] != target) {
                return -1;
            }
            return l;
        }

        private int findRight(int[] nums, int target) {
            int l = 0, r = nums.length - 1;
            while (l <= r) {
                int mid = l + (r - l) / 2;
                if (target >= nums[mid]) {
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }
            // target 太小 || 不存在
            if (r == -1 || nums[r] != target) {
                return -1;
            }
            return r;
        }

        public int[] searchRange(int[] nums, int target) {
            int[] res = new int[2];
            res[0] = findLeft(nums, target);
            res[1] = findRight(nums, target);
            return res;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}